package com.leetcode.algorithm.y22.m07.w3;

/**
 * 67. 二进制求和
 * 
 * https://leetcode.cn/problems/add-binary/
 * 
 * @author jie.deng
 *
 */
class Question0067Solution01 {
	
	public String addBinary(String a, String b) {
		int lenA = a.length();
		int lenB = b.length();
		int idxA = lenA - 1;
		int idxB = lenB - 1;
		int carry = 0;
		char[] arr = new char[Math.max(lenA, lenB) + 1];
		int idx = arr.length - 1;
		while (idxA >= 0 && idxB >= 0) {
			int sum = (a.charAt(idxA) - '0') + (b.charAt(idxB) - '0') + carry;
			arr[idx] = (char) (sum % 2 + '0');
			carry = sum / 2;
			idx--;
			idxA--;
			idxB--;
		}
		while (idxA >= 0) {
			int sum = (a.charAt(idxA) - '0') + carry;
			arr[idx] = (char) (sum % 2 + '0');
			carry = sum / 2;
			idx--;
			idxA--;
		}
		while (idxB >= 0) {
			int sum = (b.charAt(idxB) - '0') + carry;
			arr[idx] = (char) (sum % 2 + '0');
			carry = sum / 2;
			idx--;
			idxB--;
		}
		arr[0] = (char) (carry + '0');
		String str = String.valueOf(arr);
		if (arr[0] == '0') {
			return str.substring(1);
		}
		return str;
	}
    
}